#include <mutex>
#include <memory>
#include <condition_variable>

/*
    基于锁和链表的线程安全队列，
    提供了4个出队列方法，一个入队列方法
*/

template<typename T>
class thread_safe_queue
{
// 数据域
private:
    struct node
    {
        std::shared_ptr<T> data;
        std::unique_ptr<node> next;
    };

    std::mutex head_mutex;
    std::unique_ptr<node> head;
    std::mutex tail_mutex;
    node* tail;
    std::condition_variable data_cond;

// 完成队列功能函数的基础函数，不暴露在外
public:
    std::shared_ptr<T> wait_and_pop()
    {
        std::unique_ptr<node> const old_head = wait_pop_head();
        return old_head->data;
    }
private:
    // 对这两个wait_pop_head函数来说，需要确保同一个锁在执行与wait_pop_head()
    // 弹出队列头元素
    std::unique_ptr<node> wait_pop_head()
    {
        std::unique_lock<std::mutex> head_lock(wait_for_data());  // 4
        return pop_head();
    }
private:
    // 等待队列中有数据弹出的结点
    std::unique_lock<std::mutex> wait_for_data()
    {
        std::unique_lock<std::mutex> head_lock(head_mutex);
        // 使用Lambda函数对条件变量进行等待
        data_cond.wait(head_lock, [&]{return head.get() != get_tail();});
        // 将锁的实例返回给调用者
        return std::move(head_lock);
    }


public:
    void wait_and_pop(T& value)
    {
        std::unique_ptr<node> const old_head = wait_pop_head(value);
    }
private:
    // 弹出队列的头元素，并把这个元素移动到传入的参数T & value中
    std::unique_ptr<node> wait_pop_head(T& value)
    {
        std::unique_lock<std::mutex> head_lock(wait_for_data());  // 5
        value = std::move(*head->data);
        return pop_head();
    }


public:
    // 如果队列中没有元素，返回空指针
    // std::shared_ptr<T> try_pop() ==> std::unique_ptr<node> try_pop_head() ==> std::unique_ptr<node> pop_head()
    std::shared_ptr<T> try_pop()
    {
        std::unique_ptr<node> old_head = try_pop_head();
        return old_head ? old_head->data : std::shared_ptr<T>();
    }
private:
    std::unique_ptr<node> try_pop_head()
    {
        // 出队列，只需对队列的头节点mutex加锁
        std::lock_guard<std::mutex> head_lock(head_mutex);
        if(head.get() == get_tail())
        {
            return std::unique_ptr<node>();
        }
        return pop_head();
    }
private:
    // 弹出头结点
    // 还有一点要注意，std::unique_ptr<?>是不可复制的
    // 为什么这里返回了std::unique_ptr<?>呢？因为
    // 这里的std::unique_ptr<?>类型的old_head是个临时
    // 的变量，函数退出时析构了，所以调用这个函数的
    // 可以接收一个std::unique_ptr<?>对象
    // 这是一个特例，在C++ primer 418页 有提到
    std::unique_ptr<node> pop_head()
    {
        std::unique_ptr<node> old_head = std::move(head);
        head = std::move(old_head->next);
        return old_head;
    }


public:
    // bool try_pop(T& value) ==> std::unique_ptr<node> try_pop_head(T& value) ==> std::unique_ptr<node> pop_head()
    bool try_pop(T& value)
    {
        std::unique_ptr<node> const old_head = try_pop_head(value);
        return old_head;
    }
    
private:
    std::unique_ptr<node> try_pop_head(T& value) // 可上锁和等待的线程安全队列——try_pop()和empty()
    {
        std::lock_guard<std::mutex> head_lock(head_mutex);
        if(head.get() == get_tail())
        {
            return std::unique_ptr<node>();
        }
        value = std::move(*head->data);
        return pop_head();
    }


private:
    bool empty()
    {
        std::lock_guard<std::mutex> head_lock(head_mutex);
        return (head.get() == get_tail());
    }

    // 线程安全的获得队列的尾部节点
    node* get_tail()
    {
        // 获得 队列尾虚拟node的指针，需要对 队列尾的mutex 加锁
        std::lock_guard<std::mutex> tail_lock(tail_mutex);
        return tail;
    }

// 在队列尾部加入新的节点
public:
    void push(T new_value)
    {
        std::shared_ptr<T> new_data(std::make_shared<T>(std::move(new_value)));
        // 因为本来的队列尾虚拟node要指向一个数据项了，因此这里新建一个队列尾虚拟node                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                       
        std::unique_ptr<node> p(new node);
        {
            // 在队列尾部插入新的节点，只用对 队列尾的mutex 加锁
            std::lock_guard<std::mutex> tail_lock(tail_mutex);
            tail->data = new_data;
            node* const new_tail = p.get();
            tail->next = std::move(p);
            tail = new_tail;
        }
        data_cond.notify_one();
    }

// 构造函数
public:
    thread_safe_queue(): head(new node),tail(head.get()) {}
    // 不允许 拷贝构造
    thread_safe_queue(const thread_safe_queue& other) = delete;
    // 不允许 赋值操作
    thread_safe_queue& operator=(const thread_safe_queue& other) = delete;
};
